In the traditional Traveling Salesman Problem (TSP), a traveling salesman must visit customers in a number of cities and he knows the distance between pairs of cities he wants to visit. Since he is interested in not being too long on the road, he wants to take the shortest tour. FIG. 1 shows a number of cities to be visited in a traditional TSP. Suppose a traveling salesman must visit the following 8 capitol cities shown in FIG. 1: (a) Boise, Id.; (b) Salt Lake City, Utah; (c) Phoenix, Ariz.; (d) St. Paul, Minn.; (e) Columbus, Ohio; (f) Jefferson City, Mo.; (g) Richmond, Va.; and (h) Austin, Tex. FIG. 2 shows the shortest tour between the cities shown in FIG. 1 starting with a (Boise, Id.) and ending with a (Boise, Id.). The shortest tour is represented by the ordering a, b, c, h, f, g, e, d, which means he starts in city a (Boise, Id.), then goes to cities b, c, h, f, g, e, and d in that order (Salt Lake City, Utah to Phoenix, Ariz. to Austin, Tex. to Jefferson City, Mo. to Richmond, Va. to Columbus, Ohio to St. Paul, Minn.) and returning to city a (Boise, Id.). However, for various real-world applications of the TSP, there is a need for a modified solution to the TSP that starts and ends in different cities. FIG. 3 shows an alternate solution of the TSP shown in FIG. 1 in which the tour a, b, c, h, f, d, e, g begins and ends in different cities.
Furthermore, the tour shown in FIG. 2 is an idealized solution. FIG. 4 shows a more realistic example solution of the TSP than the example solution shown in FIG. 2. To travel by road would require a more roundabout path. For example, one would probably take highway 84 East from Boise, Id. to Salt Lake City, highways 15 South, 93 South and 40 East to Phoenix, Ariz., highways 17 North, 40 East, 287 South, and 35 South to Austin, Tex., back on highway 35 North to highways 75 North 69 North, 44 East, 73 North, and 54 North to Jefferson City, Mo., highways 54 North, 70 East, and 64 East to Richmond, Va., back on highway 64 West to highways 81 North and 70 West to Columbus, Ohio, highways 70 West, 65 North, 80 West, 39 North, 90 North, and 94 West to St. Paul, Minn. and highways 94 West, 15 South, 86 West, and 84 West back to Boise, Id. Also, extra time would be needed on slower roads, such as roads with construction or roads through large cities at rush hour. Travel by plane, boat, or train also has certain routes, congestion, and delays. There is a need for a solution to the TSP that takes into account the actual or realistic traveling distance, costs and time.
The TSP is an optimization problem, which is concerned with choosing the best among all possible arrangements, according to some criteria, such as distance, time, and traveling expenses. Therefore, it is not sufficient to find an arbitrary solution; instead one is interested in the best—or at least a very good—solution. However, it is not practical to enumerate all possible ordered paths for a large number of cities in order to determine the absolute best one. For a tour of n cities, the enumeration would have n! (n-factorial) ordered paths, where n!=n×(n−1)×(n−2)× . . . ×1. The function n-factorial increases exponentially. For example, the enumeration of all possible paths for 8 cities is 8!=8×7×6×5×4×3×2×1=40,320. For 100 cities, the enumeration of all possible path is 100!, which is approximately 9.3×10157 (which is “93” followed by 156 zeros). If a method enumerated one hundred million paths per second, i.e., at 100 MIPS, the speed of a typical PC, it would take approximately 2.9×10144 years to enumerate all of them! (2.9×10144 years is approximately=9.3×10157 paths÷(1,000,000 paths/sec×60 sec/min×60 min/hr×24 hr/day×365 days/yr).) Clearly, there is a need to produce a result while we are still alive. The TSP has been called an NP-hard problem because no method exists for computing the solution in polynomial time. Polynomial time means a computer running time or an order of complexity of O(nk) or better, where k is a constant. There is a need for a method for solving the TSP in polynomial time.
Various methods have tried to solve the TSP. These methods can be broadly classified as heuristic methods, natural optimization techniques (such as linear programming, mixed integer programming, and quadratic programming), neural networks, and techniques based on Boltzman machines, such as simulated annealing. Heuristic and natural optimization techniques only give local optima rather than global optima, their order of complexity is O(n!) and they are unstable when a large number of cities are considered. Neural networks are dependent on a training methodology. Simulated annealing gives a solution, but in doing so it takes a lot of time or is slow at arriving at the solution for a large number of cities. There is a need for a method that gives a solution in less time for any number of cities, with complexity of O(n+k), where k is a constant.
For these and other reasons, there is a need for the present invention.